Trong đồ thị vô hướng, đường đi rộng nhất giữa hai đỉnh chính là đường đi giữa chúng trên cây bao trùm lớn nhất của đồ thị, và đường đi minimax giữa hai đỉnh chính là đường đi trên cây bao trùm nhỏ nhất.[7][8][9]

Trong bất kì đồ thị nào, dù có hướng hay vô hướng, đều có thể áp dụng thuật toán đơn giản sau để tìm đường đi rộng nhất sau khi đã biết trọng số nhỏ nhất trên đường đi đó: xóa tất cả các cung có trọng số nhỏ hơn và tìm đường đi trên các cung còn lại bằng tìm kiếm theo chiều rộng hoặc tìm kiếm theo chiều sâu. Dựa trên ý tưởng này, có thể xây dựng một thuật toán chạy trong thời gian tuyến tính để tìm đường đi rộng nhất từ s đến t mà không cần đến cây bao trùm lớn nhất. Ý tưởng chính của thuật toán là tìm trọng số trung vị trong đồ thị, rồi kiểm tra xem có tồn tại đường đi rộng hơn giá trị trung vị hay không theo phương pháp trên. Nếu đường đi tồn tại, thì xóa hết các cung nhỏ hơn giá trị trung vị. Nếu đường đi không tồn tại, thì hợp mỗi thành phần liên thông tạo bởi các cung lớn hơn lại thành một đỉnh. Trong cả hai trường hợp, thuật toán tiếp tục trên đồ thị nhỏ hơn mới thu được.[8][10][11]